from typing import List
# 超时
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        if length < 3:
            return []

        nums.sort()
        minv, maxv = nums[0], nums[-1]
        result = set()
        i = 0
        while i < length:
            vi = nums[i]
            j = i + 1
            while j < length:
                vj = nums[j]
                if vi + vj < -maxv:
                    break
                elif vi + vj > -minv:
                    break
                else:
                    diff = 0 - vi - vj
                    includeDiff = self.search(nums, diff, i, j)
                    if includeDiff:
                        item = sorted([vi, vj, diff])
                        result.add(tuple(item))
                    j += 1
            i += 1
        return [list(t) for t in result]

    def search(self, nums: list, v: int, i1: int, i2: int):
        try:
            nums.index(v, 0, i1)
            return True
        except ValueError:
            try:
                nums.index(v, i1 + 1, i2)
                return True
            except ValueError:
                try:
                    nums.index(v, i2 + 1)
                    return True
                except ValueError:
                    return False

solu = Solution()
print(solu.threeSum([-1, 0, 1, 2, -1, -4]))